package 力扣_树算法.遍历;



import java.util.*;

/**二叉树的中序遍历
 * @author zx
 * @create 2022-04-09 11:02
 */
public class 二叉树的中序遍历_94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        //中序遍历：左根右，借助栈栈这个结构，第二次访问根节点时才能输出根节点值
        //为了知道啥时候是第二次访问，引入了node引用，从root开始一路向左子树走到头(null) - 第一次访问
        //此时栈顶保存了最后一个没有左子树的节点(第二次访问)
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(!stack.isEmpty() || root != null){
            //不管三七二十一,先一路向左走到根儿~
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //此时node为空,说明走到了null,此时栈顶就存放了左树为空的节点
            root = stack.pop();
            res.add(root.val);
            //继续访问右子树
            root = root.right;
        }
        return res;
    }
    /**
     * @return 递归
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        //递归
        List<Integer> res = new ArrayList<>();
        inOrder(root,res);
        return res;
    }
    private void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }
}
